package com.data.basic.chapter11;

/**
 *
 * 路径压缩  在find中路径压缩；
 *
 * @author wang on 2018/7/4.
 */
public class UnionFind5 implements UF {
    private int [] parent;
    private int [] rank;//rank[i]表示以i为根的集合中元素的等级，在执行路径压缩之后，rank并没有维护；

    public UnionFind5(int size) {
        this.parent = new int[size];
        rank = new int[size];
        for (int i=0;i<size;i++){
            parent[i] = i;
            rank[i] = 1;//初始值为1
        }

    }
    public int getSize(){
        return parent.length;
    }

    //查找过程，查找元素p所对应的集合编号
    //查找根节点  时间复杂度O(h)
    private int find(int p){
        if (p<0||p>=parent.length){
            throw  new IllegalArgumentException("p is out of bound!");
        }
        while (p!=parent[p]){//如果不成立就表示，p为根节点，因为根节点永远指向自己
            parent[p] = parent[parent[p]];//当前的节点的父亲节点指向该节点父亲的父亲节点   路径压缩
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p)==find(q);
    }


    //时间复杂度O(h)
    //根据两个元素所在树的rank不同判断合并方向
    //将rank低的集合合并到元素rank高的集合中去
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot==qRoot){
            return;
        }
        if (rank[pRoot]< rank[qRoot]){
            parent[pRoot] = qRoot;//qRoot不用改变rank

        }else if (rank[qRoot]<rank[pRoot]){
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[qRoot]+=1;//rank需要改变了

        }


    }
}
